/**
 * Copyright (c) 2010 Claudio Imbrenda.
 * This program is released under the terms of the GNU GPL License, version 3 or later.
 */
 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>        /* For mode constants */
#include <fcntl.h>           /* For O_* constants */
#include <sys/types.h>
                     

#include "graph.h"


/** Creates an empty graph with the given number of nodes.
 * @param size the number of nodes.
 * @return a pointer to the new graph.
*/
struct tngraph* mkgraph(uint size){
 int cx;
 struct tngraph* res = malloc(sizeof(struct tngraph));

 res->size = size;
 res->nodes = malloc(size*sizeof(struct tnnode));

 for(cx=0;cx<size;cx++){
   res->nodes[cx].size=0;
   res->nodes[cx].neighbours=NULL;   
 }
 
 return res;
}


/** Initializes a given node. 
 @param this the graph
 @param node the node to be initialized
 @param nneigh number of neighbours.
*/
void initnode(struct tngraph*this, uint node, uint nneigh){
 if(this->nodes[node].neighbours!=NULL){fprintf(ERR,"node %u was already initialized!\n",node);abort();}
 if(nneigh>0)
  this->nodes[node].neighbours = malloc(nneigh*sizeof(int));
 else
  this->nodes[node].neighbours = NULL;
}

/** Frees a node.
 @param this the graph
 @param node the node to free. All allocated memory for this node will be
 freed. If the graph was loaded from shared memory, no memory is actually
 freed.  In any case the size field will be set to 0 and the neighbours
 will be set to NULL.
*/
void freenode(struct tngraph*this, uint node){
 this->nodes[node].size=0;
 if(this->graphtype!=GRAPH_MODE_MMAP) /* Free only if it's not MMAPped */
   free(this->nodes[node].neighbours);
 this->nodes[node].neighbours=NULL;
}


/** Frees a graph. All the nodes will be freed with freenode().
 @param this the graph to be freed.
*/
void freegraph(struct tngraph*this){
 uint cx;
 if(this==NULL)return;
 for(cx=0;cx<this->size;cx++)
   freenode(this,cx);
 free(this->nodes);
 free(this);
}

/** Adds an edge from node1 to node2, and vice versa.
*/
static int addedge(struct tngraph*this, uint node1, uint node2){
 struct tnnode*n1,*n2;
 n1=GETNODE(this,node1);
 n2=GETNODE(this,node2);
 /* Some sanity checks: */
 if(n1->neighbours==NULL){fprintf(ERR,"node %u has NULL neighbours.\n",node1);abort();}
 if(n2->neighbours==NULL){fprintf(ERR,"node %u has NULL neighbours.\n",node2);abort();}
 n1->neighbours[n1->size]=node2;
 n1->size++;
 n2->neighbours[n2->size]=node1;
 n2->size++;
 return 0;
}


/* Helper for qsort */
static int uintcompare(const void*f,const void*s){
 register int a=(signed)(*(uint*)f);
 register int b=(signed)(*(uint*)s);
 return a-b;
}


/** Tests whether an edge exists between two given nodes.
 @param this the graph
 @param node1 the first node
 @param node2 the second node
 @return 1 if there is an edge between node1 and node2, 0 otherwise
*/
int existsedge(struct tngraph*this, uint node1, uint node2){
 struct tnnode*n;
 uint*b;
 n=GETNODE(this,node1);
 if(n->neighbours==NULL)abort();
 b=(uint*)bsearch(&node2,n->neighbours,n->size,sizeof(uint),uintcompare);
 if(b==NULL)return 0;
 return 1;
}


/** Returns the number of actual nodes in the graph.
 @param this the graph
*/
int nodecount(struct tngraph*this){
 int cx;
 int res=0;
 
 for(cx=0;cx<this->size;cx++)
  if((this->nodes[cx].size)!=0) res++; /* We count only existent nodes */
 
 return res;
}


/** Returns the number of edges in the graph.
 @param this the graph
*/
long long edgecount(struct tngraph*this){
 int cx;
 long long res=0;

 for(cx=0;cx<this->size;cx++)
   res+=this->nodes[cx].size;

 return res;
}



/* Helper function to sort the neighbours of every node */
static void sortedges(struct tngraph*g){
 int cx;
 for(cx=0;cx<g->size;cx++)
   qsort(g->nodes[cx].neighbours,g->nodes[cx].size,sizeof(uint),uintcompare);
}


/* Helper function to load a graph from a POSIX shared memory segment */
static struct tngraph*loadmmapgraph(const char*handle){
 struct tngraph*res=NULL;
 int fd,a,cx,tmp;
 long long size=0;
 uint*mm;
  
 fd=shm_open(handle,O_RDONLY,S_IRUSR);
 if(fd==-1){
  perror("error opening SHM segment");
  return NULL;
 }
 tmp=read(fd,&a,sizeof(uint));
 if(tmp!=sizeof(uint)){fprintf(ERR,"invalid SHM format");return NULL;}
 res = mkgraph(a);
 res->graphtype=GRAPH_MODE_MMAP;
 
 for(cx=0;cx<a;cx++){
   /* Reads the degree of the node directly from the file */
   tmp=read(fd,&(res->nodes[cx].size),sizeof(uint));
   if(tmp!=sizeof(uint)){fprintf(ERR,"invalid SHM format");return NULL;}
   size += res->nodes[cx].size;
 }
 lseek(fd,0,SEEK_SET); /* maybe useless */
 
#ifdef MMAP_HAS_HUGETLB
 mm = mmap(NULL, (size_t)((size+a+1)*4), PROT_READ, MAP_SHARED|MAP_HUGETLB, fd, 0);
#else
 mm = mmap(NULL, (size_t)((size+a+1)*4), PROT_READ, MAP_SHARED, fd, 0);
#endif
 fprintf(ERR,"mmap: %p.",mm);
 if(mm==MAP_FAILED){
  perror("SHM mmap failed");
  freegraph(res);
  return NULL;
 }
 
 /* get the neighbours of the first node */ 
 res->nodes[0].neighbours = mm+a+1;
 
 for(cx=1;cx<a;cx++) /* set the correct pointer for all the nodes */
  res->nodes[cx].neighbours=res->nodes[cx-1].neighbours+res->nodes[cx-1].size;
 
 for(cx=0;cx<a;cx++)
  if(res->nodes[cx].size==0)res->nodes[cx].neighbours=NULL;
 
 return res;
}


/** Loads a graph from a file or from a POSIX shared memory segment.
 @param file the name of the file or or POSIX SHM handle
 @param mode the loading mode: GRAPH_MODE_TEXT for the text format,
  GRAPH_MODE_BINARY for the binary format, GRAPH_MODE_MMAP for the POSIX
  Shared Memory mode.
 @return a pointer to a new graph, or NULL in case of errors.
*/
struct tngraph* loadgraph(const char * file, uint mode){
 struct tngraph* res=NULL;
 FILE* inf;
 uint a,b;
 int cx,tmp;
 
 if(mode>GRAPH_MODE_MMAP)return NULL; /* invalid mode */

 /* if we are mmapping from SHM, we call the helper function */ 
 if(mode==GRAPH_MODE_MMAP) return loadmmapgraph(file);
 
 inf=fopen(file,"r");
 if(inf==NULL)return NULL;

 /* the two formats are almost the same; the only difference is that one is
 binary and the other is textual, the structure is the same */
 
 /* read the number of nodes */
 switch(mode){
 case GRAPH_MODE_TEXT:
  cx=fscanf(inf,"%u\n",&a);
  if(cx==EOF) goto fail;
  break;
 case GRAPH_MODE_BINARY:
  cx=fread(&a,sizeof(int),1,inf);
  if(cx!=1) goto fail;
  break;
 default: goto fail;
 }
 
 fprintf(ERR,"|%u|..",a);
 res = mkgraph(a);
 res->graphtype=mode;
 
 /* read the degree of each node and perform initialization */
 for(cx=0;cx<res->size;cx++){
  switch(mode){
  case GRAPH_MODE_TEXT:
   if((tmp=fscanf(inf,"%u %u\n",&a,&b))==EOF)goto fail;
   if(tmp!=2)goto fail;
   break;
  case GRAPH_MODE_BINARY:
   if(fread(&a,sizeof(int),1,inf)!=1) goto fail;
   if(fread(&b,sizeof(int),1,inf)!=1) goto fail;
   break;
  default: goto fail;
  }

  if(a!=cx) goto fail;
  initnode(res,a,b);
 }
 
 fprintf(ERR,"...");
 
 /* read the edges */
 switch(mode){
 case GRAPH_MODE_TEXT:
  while((tmp=fscanf(inf,"%u %u\n",&a,&b))!=EOF){
   if(tmp!=2) goto fail;
   addedge(res,a,b);
  }
  break;
 case GRAPH_MODE_BINARY:
  while(!feof(inf)){
   tmp=fread(&a,sizeof(int),1,inf);
   if(tmp==0){
    if(!feof(inf)) goto fail;
   }else{
    if(fread(&b,sizeof(int),1,inf)!=1) goto fail;
    addedge(res,a,b);
   }
  }
  break;
 default: goto fail;
 }

 fclose(inf);
 
 sortedges(res);
 
 return res;
 
fail:
 freegraph(res); 
 fclose(inf);
 return NULL;
}

/** Returns a valid random node from the graph. 
 @param g the graph
 @return a valid random node.
*/
uint getrandomnode(struct tngraph*g){
 uint res;
 do{
  res= (uint)(random() % g->size);
 }while(GETNODE(g,res)==NULL);
 return res;
}

/** Returns a valid random unmarked node from the graph. 
 @param g the graph
 @return a valid random node.
*/
uint getrandomunmarkednode(struct tngraph*g,unsigned char*marks){
 uint res;
 do{
  res= (uint)(random() % g->size);
 }while((GETNODE(g,res)==NULL)||(ISMARKED(res,marks)));
 return res;
}
